#!/usr/bin/python
#example code, lecture 12
#Lecture 12: More about debugging, knapsack problem, introduction to dynamic programming

def fib( n ):
    global numCalls
    numCalls += 1
    #print 'fib called with', n
    if n <= 1:
        return 1
    else:
        #print 'return fib(', n, '-1 ) +', 'fib(', n, '-2 )'
        return fib( n-1 ) + fib( n-2 )
numCalls = 0
#fib( 5 )

n = 10
print 'fib of', n, '=', fib( n ), 'numCalls', numCalls
